These class of algorithms takes a Graph as input, and generates Tree, which consists of some of edges of input Graph, which are selected according to particular criteria. Some examples are
import
statement
In [6]:
import openanalysis.tree_growth as TreeGrowth
networkx
graphdef algorithm_name(G,source = None):
if source is None:
source = G.nodes()[0]
# do other work now
v
is visited from node u
, yield
the tuple containing them# Assume that visiting is done
yield (u,v)
OpenAnalysis.base_data_structures
In [7]:
from openanalysis.base_data_structures import PriorityQueue
Now, Let's implement the algorithm
In [8]:
def dijkstra(G, source=None): # This signature is must
if source is None: source = G.nodes()[0] # selecting root as source
V = G.nodes()
dist, prev = {}, {}
Q = PriorityQueue()
for v in V:
dist[v] = float("inf")
prev[v] = None
Q.add_task(task=v, priority=dist[v])
dist[source] = 0
Q.update_task(task=source, new_priority=dist[source])
visited = set()
for i in range(0, len(G.nodes())):
u_star = Q.remove_min()
if prev[u_star] is not None:
yield (u_star, prev[u_star]) # yield the edge as soon as we visit the nodes
visited.add(u_star)
for u in G.neighbors(u_star):
if u not in visited and dist[u_star] + G.edge[u][u_star]['weight'] < dist[u]:
dist[u] = dist[u_star] + G.edge[u][u_star]['weight']
prev[u] = u_star
Q.update_task(u, dist[u])
Note how implementation looks similiar to the algorithm, except the if
block, which is used to yield
the edges.
apply_to_graph(fun)
: Creates Random Geometric Graph of 100 nodes and applies fun
on it to build the tree. After building the tree, it shows original graph and the tree side by sidetree_growth_visualizer(fun)
: Creates Random Geometric Graph of 100 nodes and applies fun
on it to build the tree. Saves the animation of building the tree in output/
folderRandom Geometric Graph is created using two parameters. Number of nodes $n$, and radiuus $r$. $n$ points are chosen randomly on plane. The edge between 2 nodes is created if and only if the distance between 2 nodes is less than $r$
import networkx as nx
G = nx.random_geometric_graph(100,2.3) # n,r
pos = nx.get_node_attribute('pos')
In [10]:
TreeGrowth.apply_to_graph(dijkstra)
After executing
TreeGrowth.tree_growth_visualizer(dijkstra)
go to output/
directory to see mp4
files
You can see more examples at Github